<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>插入排序</title>
</head>
<body>
<script>
  // 平均时间复杂度 O(n^2)
  // 插入排序
  function insertSort(array, target) {
    let length = array.length
    // 如果是空数组(第一个) 则直接push
    if(length === 0){
      array.unshift(target)
      return
    }
    // 插入排序
    for(let i = length - 1;i >= 0; i--) {
      if(array[i] < target){
        // 在后面插入
        array.splice(i+1, 0, target)
        break
      }
      // 如果是最小的 直接放到最前面
      if(i === 0){
        array.unshift(target)
      }
    }
  }
  // 主程序
  function sort(array) {
    let result = []
    for(let i = 0;i < array.length;i ++) {
      insertSort(result, array[i])
    }
    return result
  }
  let arr = []
  // 随机生成乱序数组
  for(let i = 0;i < 30;i ++){
    arr.push(Math.floor(Math.random() * 90))
  }
  console.log(sort(arr))
</script>
</body>
</html>
